public class LongestUnivaluePath {

    int ans = 0;
    public int longestUnivaluePath1(TreeNode root) {
        dfs(root, 1001);
        return ans;
    }

    public int dfs(TreeNode node, int last) {
        if (node == null) return 0;
        int l = dfs(node.left, node.val);
        int r = dfs(node.right, node.val);
        ans = Math.max(ans, l + r);
        if (last == node.val) return Math.max(l, r) + 1;
        return 0;
    }


    int temp = 0;
    public int longestUnivaluePath(TreeNode root) {
        process1(root);
        return temp;
    }

    public int process1(TreeNode root) {
        if (root == null) return 0;
        int l = process1(root.left);
        int r = process1(root.right);
        int res = 0;
        int a = -1;
        if (root.left != null && root.left.val == root.val) {
            a = l;
            res += l + 1;
        }
        if (root.right != null && root.right.val == root.val) {
            a = Math.max(a, r);
            res += r + 1;
        }
        temp = Math.max(temp, res);
        return a == -1 ? 0 : a + 1;
    }
}
